\section{Algorithm}\label{sec:alg}

The algorithm consists of two major components: constraint propagation and backtracking search. In fact, the constraint propagation step is incorporated into the backtracking search. Some puzzles can be solved with just an application of the constraint propagation. Some puzzles require ``sophisticated'' rules (e.g. naked triples) to solve with just constraint propagation. Other puzzles require search and backtracking.

\subsection{Constraint Propagation}

The constraint propagation step applies the following rules to the SuDoKu board in this order to reduce the domain values for variables:

\begin{description}
	\item[Rule 1] Assign to any cell a value $x$ if it is the only value left in its domain.
	\item[Rule 2] Assign to any cell a value $x$ if $x$ is not in the domain of any other cell in that row, column or box.
	\item[Rule 3] In any row, column or box, find $k$ squares that each have a domain that contains the same $k$ numbers or a subset of those numbers. Then remove those $k$ numbers from the domains of all other cells of that unit. (Called the ``naked double'' and ``naked triple'' rule for $k=2$ and $k=3$ respectively.)
\end{description}

Afterwards, these rules are ``propagated'' across the board, updating the board to be consistent with the new assignments. The process repeats until the board no longer updates (converges) or a variable is found to have an empty domain (contradiction).

In our experiments section, we will show the performance of the constraint propagation step when toggling a subset of these rules on or off.

\begin{algorithm}[H]
\caption{Constraint Propagation}
\label{constraint}
\begin{algorithmic}
\STATE function CONSTRAINT-PROPAGATION(puzzle)
\WHILE{any variable's domain was updated}
	\STATE perform rule one
	\STATE perform rule two
	\STATE perform naked doubles and triple rules
	\FOR{square in puzzle}
		\IF{domain is empty}
			\RETURN failure
		\ENDIF

		\IF{domain is exactly one value}
			\FOR{sq in square.neighbors along row, column and box}
				\STATE remove square.value from sq's domain
			\ENDFOR
		\ENDIF
	\ENDFOR
\ENDWHILE
\end{algorithmic}
\end{algorithm}

\subsection{Backtracking Search}

Backtracking search is a depth first search algorithm. For each step of the algorithm, it picks a variable to assign a value and then performs constraint propagation as described above. If there is a contradiction after the constraint propagation step, the search discards that assignment and backtracks, making an alternative assignment. If the constraint propagation step was successful, then the search continues making another assignment. The search continues until it finds a complete assignment that satisfies the puzzle, otherwise returns a failure.

There are several heuristics that can be implemented for the backtracking search. For our project, there are two different heuristics for choosing the variable to assign:

\begin{enumerate}
	\item Pick the most constrained square (i.e. the variable with the least number of domain values other than those already assigned)
	\item Pick any random square
\end{enumerate}

In fact, the first heuristic performs better than the second heuristic in general constraint satisfication problems because choosing an assignment from the most constrained variable will help prune the search tree faster. We will demonstrate the validity of this theory in our experiments.

In the pseudocode, SELECT-UNASSIGNED-VARIABLE is a heuristic function. In our experiment, we implemented the random slot heuristic and most constrained heuristic. Note that in our implementation, we take advantage of creating copies of puzzle states so that upon backtracking, we simply discard the entire state rather than undoing an assignment.

\begin{algorithm}[H]
\caption{Backtracking Search}
\label{backtrack}
\begin{algorithmic}
\STATE function BACKTRACK(assignment, puzzle)
\IF{assignment is complete}
	\RETURN assignment
\ENDIF
\STATE var = SELECT-UNASSIGNED-VARIABLE(puzzle)
\FOR{value in var.domain}
	\IF{value is consistent with assignment}
		\STATE add {var = value} to assignment
		\STATE update puzzle to new assignment
		\STATE inferences = CONSTRAINT-PROPAGATION(puzzle)
		\IF{inferences is not failure}
			\STATE add inferences to assignment
			\STATE result = BACKTRACK(assignment, puzzle)
			\IF{result is not failure}
				\RETURN result
			\ENDIF
		\ENDIF
	\ENDIF
	\STATE remove {var = value}
	\STATE remove inferences from assignment
\ENDFOR
\RETURN failure
\end{algorithmic}
\end{algorithm}

%\begin{algorithm}[H]
%\caption{A* Search}
%\label{alg1}
%\begin{algorithmic}
%\STATE exploredSet = $\emptyset$ 
%\STATE frontier = [initialPath]
%\WHILE{number(explored) $<$ NMAX}
%\IF{frontier == $\emptyset$}
%    \RETURN FALSE
%\ENDIF
%\STATE path = frontier.pop()
%\STATE state = path[0]
%\STATE exploredSet.add(state)
%\IF{state == goalState}
%    \RETURN path
%\ENDIF
%\FOR{action in state.validActions()}
%    \FOR{newState in action.results()}
%        \STATE newPath = path + newState
%        \IF{ismember(frontier,newPath) == FALSE}
%            \STATE frontier.push(newPath)
%        \ENDIF
%    \ENDFOR
%\ENDFOR
%\ENDWHILE
%\end{algorithmic}
%\end{algorithm}

